#ifndef DIJ_H
#define DIJ_H
#define INF 100000
#include<QVector>
#include<QQueue>
#include<queue>

#endif // DIJ_H
const int MAXN=50;
const int n=23;
int s[MAXN];
int Edge[MAXN][MAXN];
int path[MAXN];
int shortest[MAXN];
bool visit[MAXN];//是否已经被选作为基点
struct node{
    int p, w;
    node(int a, int b):p(a), w(b){}
    bool operator< (const node& b) const
    {
        return w > b.w;
    }
    bool operator >(const node& b) const
    {
        return w>b.w;
    }
};
class Map{
public:
    int se[MAXN];
    int ke;
    int dis[MAXN];
    int buite[MAXN];  //表示该点的属性

    void Dijkstra(int v0);
    void Dijkstra_dui(int start);
    Map();
};
Map::Map(){
    for(int i=1;i<=23;i++){
        for(int j=1;j<=23;j++){
            if(i!=j)
                Edge[i][j]=INF;
            else
                Edge[i][j]=0;
        }
    }
    Edge[2][1]=177;Edge[2][3]=292;
    Edge[2][23]=152;Edge[2][22]=253;
    Edge[2][4]=310;Edge[2][11]=150;
    Edge[3][23]=174;Edge[3][5]=189;
    Edge[3][9]=282;Edge[3][1]=143;
    Edge[22][21]=104;Edge[21][20]=125;
    Edge[20][19]=206;Edge[20][5]=156;
    Edge[21][5]=180;Edge[19][5]=170;
    Edge[19][8]=172;Edge[19][18]=270;
    Edge[18][8]=158;Edge[8][6]=130;
    Edge[18][17]=304;Edge[17][10]=144;
    Edge[10][6]=308; Edge[10][7]=383;
    Edge[10][16]=142;Edge[16][15]=130;
    Edge[15][14]=143;Edge[15][13]=200;
    Edge[13][7]=194;Edge[13][9]=190;
    Edge[9][4]=201;Edge[9][1]=320;
    Edge[4][12]=230;Edge[4][11]=202;
    Edge[12][14]=368;Edge[14][15]=143;
    Edge[5][7]=393;Edge[5][6]=296;
    Edge[3][2]=292;Edge[22][23]=148;
    Edge[1][4]=156;Edge[4][1]=156;
    Edge[9][12]=103;Edge[9][7]=114;
    Edge[4][11]=202;Edge[23][3]=174;


    //定义 医院 公安局  维修点
    // 分别为 0 1 2
    buite[19]=3;  buite[15]=3; //医院
    buite[23]=2;  buite[13]=2; // 维修点
    buite[12]=1;
//    buite[11]=1; // 公安局

    for(int i=1;i<=23;i++){
        for(int j=1;j<=23;j++){
            if(Edge[j][i]!=INF)
            {
                Edge[i][j]=Edge[j][i];
            }
            else
            {
                Edge[j][i]=Edge[i][j];
            }
        }
    }
}
void Map::Dijkstra(int v0){ // 2->1
    int i,j,k;
    for(int i=1;i<=n;i++){
        dis[i]=Edge[v0][i];
        s[i]=0;
        if(i!=v0&&dis[i]<INF){
            path[i]=v0;
        }
        else
        {
            path[i]=-1;
        }
    }
    s[v0]=1; dis[v0]=0;
    for(i=1;i<n;i++)
    {
        int min=INF,u=v0;
        for(j=1;j<=n;j++){
            //选出距离最短的点u
            if(!s[j]&&dis[j]<min){
                u=j;
                min=dis[j];
            }
        }
        s[u]=1;
        for(k=1;k<=n;k++){
            if(!s[k]&&Edge[u][k]<INF&&(dis[u]+Edge[u][k])<dis[k]){
                //更新距离
                dis[k]=dis[u]+Edge[u][k];
                path[k]=u;
            }
        }
    }
}

void Map::Dijkstra_dui(int start){

}
